
public class PostOrderFromPreAndIn{
static	int search(int input[], int dataToSearch, int n)
	{
		
		for(int i = 0; i < n; i++)
		{
			if(input[i] == dataToSearch)
				return i;
		}

		return (-1);
	}

static	void postOrderFromPreAndIn(int pre[], int in[], int n, int preStart, int inStart)
	{

		int root = search(in, pre[preStart], n);

		//left subtree not empty
		if(root != 0)
		{
			
			postOrderFromPreAndIn(pre, in, root, preStart+1, inStart);
		}
		//right subtree not empty
		if(root != n-1)
		{
			postOrderFromPreAndIn(pre, in, n-root-1, preStart+root+1, inStart+root+1);
		}
		//print root
		System.out.println(pre[preStart]);
	}

	public static void  main(String args[])
	{
		int[] pre = {4,2,5,1,3,6};
		int[] in = {1,2,4,5,3,6};
		int n = in.length;
		System.out.println("-------------Postorder Traversal-----------");
		postOrderFromPreAndIn(pre,in,n,0,0);
		
	}
}